Камеры
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Между пунктами А и Б имеется автодорога. В некоторых точках вдоль неё установлено N камер контроля скорости.

В связи с завершением строительства ещё одной дороги компания, которой принадлежат камеры, приняла решение снять K из них и переместить на новую дорогу. Осталось выбрать, какие именно камеры следует снять.

Посовещавшись, эксперты компании решили, что наилучшим вариантом будет снять такие K камер, чтобы расстояние между двумя самыми близкими друг к другу оставшимися камерами получилось как можно больше. Определите, какие именно камеры следует снять в соответствии с данным критерием.

Входные данные

В первой строке входных данных записано целое число N – количество камер. Во второй строке записано целое число K – сколько камер нужно снять. В следующих N строках записаны N целых чисел в диапазоне от 0 до 109 – координаты камер. Координаты даны в порядке возрастания без повторений.

Выходные данные

В первую строку выведите одно целое число – максимально возможное расстояние между ближайшими друг к другу оставшимися камерами.

Во вторую строку выведите K различных целых чисел – номера камер, которые нужно снять. Нумерация начинается с единицы. Номера можно выводить в любом порядке. Если есть несколько верных ответов, выведите любой.

Система оценки

Подзадача 1 (до 50 баллов): 3 ≤N≤ 105, K= 1

Подзадача 2 (до 25 баллов): 3 ≤N≤ 20, 1 <K≤N- 2

Подзадача 3 (до 25 баллов): 3 ≤N≤ 105, 1 <K≤N- 2

Примеры

Входные данные

    4
    1
    40
    50
    60
    80

Выходные данные

    20
    2

Входные данные

    5
    3
    10
    20
    40
    50
    80

Выходные данные

    70
    2 3 4

Примечание

В первом примере можно убрать камеру номер 2 (с координатой 50). Тогда ближайшие друг к другу оставшиеся камеры будут находиться на расстоянии 20.

Во втором примере нужно убрать все камеры, кроме первой и последней. Тогда между оставшимися будет расстояние 70.